package algorithm.middle;

import java.util.*;
import java.util.stream.Collectors;

public class LRUCache {
    /**
     * O(1)找key
     */
    private Map<Integer, Node> map;
    private Integer capacity;
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        this.capacity = capacity;
        //注意头尾节点没有元素
        head = new Node(-300, -300);
        tail = new Node(-300, -300);
    }

    public int get(int key) {
        Node node = getNode(key);
        if (node == null) {
            return -1;
        }
        return node.val;
    }

    public void put(int key, int value) {
        if (map.isEmpty()) {
            Node node = new Node(key, value);
            head.next = node;
            node.pre = head;
            node.next = tail;
            tail.pre = node;
            map.put(key, node);
        } else {
            Node node = getNode(key);
            if (node != null) {
                node.val = value;
            } else {
                //新插入元素
                if (map.size() == capacity) {
                    //超过容量，删除队尾
                    Node remove = tail.pre;
                    map.remove(remove.key);
                    tail.pre = remove.pre;
                    remove.pre.next = tail;
                    //help gc
                    remove.next = null;
                    remove.pre = null;
                }
                //放入头节点
                node = new Node(key, value);
                map.put(key, node);
                //node不为null，移动到头部
                node.pre = head;
                node.next = head.next;
                head.next.pre = node;
                head.next = node;
            }
        }
    }

    /**
     * 获取且更新位置
     */
    private Node getNode(Integer key) {
        Node node = map.get(key);
        if (node == null) {
            return null;
        }
        //node不为null，移动到头部
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        return node;
    }

    public class Node {
        public int key;
        public int val;
        public Node pre;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }


    /**
     * ["LRUCache","put","put","get","put","get","put","get","get","get"]
     * [[2],[1,0],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
     *
     * @param args
     */
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.get(1);
        lruCache.put(3, 3);
        lruCache.get(2);
        lruCache.put(4, 4);
        lruCache.get(1);
        lruCache.get(3);
        lruCache.get(4);
        ArrayList<LRUCache.Node> list = new ArrayList<>();
         list.stream().map(o -> o.val).collect(Collectors.toList());
         Collections.reverse(list);
         list.stream().map(o -> o.val).collect(Collectors.toList());

    }
}
